#ifndef LINKQUEUE_HPP
#define LINKQUEUE_HPP

#include <cstdlib>

template <typename LinkNodeContent> struct LinkNode {
  LinkNodeContent data;
  struct LinkNode<LinkNodeContent> *next;
};

template <typename LinkNodeContent> class LinkQueue {
private:
  LinkNode<LinkNodeContent> *front, *rear; // 队头队尾
public:
  // 初始化队列
  LinkQueue() {
    front = rear =
        (LinkNode<LinkNodeContent> *)malloc(sizeof(LinkNode<LinkNodeContent>));
    front->next = nullptr;
  }

  // 判队空
  bool IsEmpty() {
    if (this->front == this->rear)
      return true;
    else
      return false;
    ;
  }

  // 将x入队
  void EnQueue(LinkNodeContent x) {
    LinkNode<LinkNodeContent> *s =
        (LinkNode<LinkNodeContent> *)malloc(sizeof(LinkNode<LinkNodeContent>));
    s->data = x;
    s->next = nullptr;
    this->rear->next = s;
    this->rear = s;
  }

  // 出队，并将值赋给x
  bool DeQueue(LinkNodeContent &x) {
    if (front == rear)
      return false;
    LinkNode<LinkNodeContent> *p = front->next;
    x = p->data;
    front->next = p->next;
    if (rear == p)
      rear = front;
    free(p);
    return true;
  }
};

#endif